In some applications, storage devices receive and store multi-channel data streams that include sequentially intermixed packets of data of different data channels. For example, a digital video recorder (DVR) may be programmed to receive a data stream that includes packets of data for multiple different channels (e.g., TV channels). In hard drive devices with moving parts, performance may be negatively impacted when intermixed channel segments of a multi-channel data stream are written according to a sequential order of receipt, as this may entail excessive seeks of an actuator arm to disparate storage media locations associated with different data channels. In these devices, write throughput may be improved by re-ordering writes to increase the time that the actuator arm spends writing to sequential physical data blocks. However, re-ordering writes poses a burden on caching resources.